package com.cqs.leetcode.link;

import com.cqs.leetcode.ListNode;
import com.cqs.leetcode.TestCaseUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lixiaowen
 * @create 2020-01-02
 */
public class RemoveDuplicatesfromSortedListII82 {


    static class Solution {
        public ListNode deleteDuplicates(final ListNode head) {
            if (head == null) return head;
            //哨兵结点 --
            final ListNode sentinel = new ListNode(head.val - 1);
            sentinel.next = head;
            ListNode pre = sentinel, cur = head, next = cur.next, newHead = null;
            while (cur != null) {
                while (next != null && next.val == cur.val) {
                    next = next.next;
                    cur = cur.next;
                }
                //判断是否有重复的元素
                if (pre.next != cur) {
                    pre.next = next;
                    //不更新pre case: 3->3->5->5->7
                } else {
                    if (pre == sentinel) {
                        newHead = cur;
                    }
                    pre = cur;
                }
                //更新cur
                cur = next;
                if (next != null) {
                    next = next.next;
                }
            }
            return newHead;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<int[]> cases = new ArrayList<>();
        cases.add(new int[]{1, 1, 9, 9});
        cases.add(new int[]{1, 1, 3, 4, 5, 7, 9, 9});
        cases.add(new int[]{3, 4, 5, 7, 9, 9, 10, 10, 11});
        cases.forEach(ints -> {
            ListNode head = ListNode.build(ints);
            head = solution.deleteDuplicates(head);
            System.out.println(TestCaseUtils.arrFormat(ints));
            System.out.println(head);
            System.out.println("\r\n");
        });

    }
}
